//
// Created by Administrator on 2021/12/30.
//

#ifndef CPP_LEARNING_LIST_HPP
#define CPP_LEARNING_LIST_HPP
#include "list_node.hpp"

template <typename T>
class List{
private:
    int _size;
    ListNodePosi(T) header;
    ListNodePosi(T) trailer;

protected:
    void init();
    int clear();
    void copyNodes(ListNodePosi(T), int);
    void merge(ListNodePosi(T)&, int ,List<T>&, ListNodePosi(T)&, int);
    void mergeSort(ListNodePosi(T)&, int);
    void selectionSort(ListNodePosi(T), int);
    void insertionSort(ListNodePosi(T), int);

public:
    List(){init();}
    List(List<T> const & L);
    List(List<T> const &L, Rank r, int n);
    List(ListNodePosi(T) p, int n);

    ~List();

    // 只读访问接口
    Rank size()const {return _size;}
    bool empty() const {return _size <= 0;}
    T& operator[](Rank r) const;

    ListNodePosi(T) first()const {return header->succ;}
    ListNodePosi(T) last() const {return trailer->pred;}
    bool valid(ListNodePosi(T) p){
        return (p) || (p!=header) || (p!=trailer);
    }

    int disordered() const;

    ListNodePosi(T) find(T const&e){
        find(e,_size,trailer);
    }
    ListNodePosi(T) find(T const&e, int n, ListNodePosi(T) p) const;

    ListNodePosi(T) search(T const& e);

    ListNodePosi(T) searchMax(ListNodePosi(T) p, int n);
    ListNodePosi(T) searchMax(){
        searchMax(header->succ, _size);
    }

    ListNodePosi(T) insertAsFirst(T const&e);
    ListNodePosi(T) insertAsLast(T const&e);

    ListNodePosi(T) insertAsSucc(ListNodePosi(T)p, T const&e);
    ListNodePosi(T) insertAsPred(ListNodePosi(T)p, T const&e);

    T remove(ListNodePosi(T) p);
    void merge(List<T>& L){
        merge(first(),_size,L,L.first(),L._size);
    }

    void sort(ListNodePosi(T) p, int n);
    void sort(){
        sort(first(),_size);
    }
    int deduplicate();
    int uniquify();
    void reverse();

    void traverse(void(*)(T&));

    template<typename VST>
    void traverse(VST&);


};

template <typename T>
void List<T>::init() {
    header = new ListNode<T>;
    trailer = new ListNode<T>;
    header->succ = trailer; header->pred = NULL;
    trailer->pred = header; trailer->succ = NULL;
    _size = 0;
}

template <typename T>
T& List<T>::operator[](Rank r) const {
    ListNodePosi(T) p = first();
    while(r>0){
        p = p->succ;
        r--;
    }
    return p->data;
}

// ===============================
// 插入
template <typename T>
ListNode<T> * List<T>::insertAsFirst(const T &e) {
    _size ++;
    return header->insertAsSucc(e);
}
template <typename T>
ListNode<T> * List<T>::insertAsLast(const T &e) {
    _size++;
    return trailer->insertAsPred(e);
}
template <typename T>
ListNode<T> * List<T>::insertAsPred(ListNode<T> *p, const T &e) {
    _size++;
    return p->insertAsPred(e);
}

template <typename T>
ListNode<T> * List<T>::insertAsSucc(ListNode<T> *p, const T &e) {
    _size ++;
    return p->insertAsSucc(e);
}


//  构造函数
template <typename T>
void List<T>::copyNodes(ListNode<T> *p, int n) {
    init();
    while (n--){
        insertAsLast(p->data);
        p = p->succ;
    }
}

template <typename T>
List<T>::List(ListNode<T> *p, int n) {
     copyNodes(p,n);
 }

template <typename T>
List<T>::List(const List<T> &L) {
    copyNodes(L.first(),L._size);
}
template <typename T>
List<T>::List(const List<T> &L, Rank r, int n) {
    copyNodes(L[r],n);
}

template <typename T>
T List<T>::remove(ListNode<T> *p) {
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    _size--;
    return e;
}

template <typename T>
int List<T>::clear() {
    int oldSize = _size;
    while (_size > 0){
        remove(header->succ);
    }
}
template <typename T>
 List<T>::~List() {
     clear();
    delete header;
    delete trailer;
 }

// ====================================================
// 遍历
template <typename T>
void List<T>::traverse(void (*visit)(T &)) {
    for(ListNodePosi(T) p=header->succ; p!=trailer; p = p->succ){
        visit(p->data);
    }
}


template <typename T>
template<typename VST>
void List<T>::traverse(VST & visit) {
    for(ListNodePosi(T) p=header->succ; p!=trailer; p = p->succ){
        visit(p->data);
    }
}


//===============================================================
// 查找
// 在无序列表(可能是trailer)的n个针前驱中，找到等于e的最后者
template <typename T>
ListNode<T> * List<T>::find(const T &e, int n, ListNode<T> *p) const {
    while(n-- > 0)
    {
        p = p->pred;
        if(e == p->data){
            return p;
        }
    }

    return NULL;
}

template <typename T>
int List<T>::deduplicate() {
    if(_size < 2) return 0;

    int oldSize = _size;
    ListNodePosi(T) p = header;
    Rank r = 0;
    while (trailer != (p = p->succ)){
        ListNodePosi(T) q = find(p->data,r,p);
        q?remove(q):r++;
    }
}


template<typename T>
int List<T>::uniquify() {
    if(_size < 2) return 0;

    int oldSize = _size;
    ListNodePosi(T) p = first(); ListNodePosi(T) q;
    while (trailer != (q = p->succ)){
        if(p->data != q->data){
            p = q;
        }else{
            remove(q);
        }
    }
}




#endif //CPP_LEARNING_LIST_HPP
